package lc.q101_150;

public class Q123 {

    public static void main(String[] args) {
        System.out.println(new Q123().maxProfit(new int[]{3,3,5,0,0,3,1,4}));
        System.out.println(new Q123().maxProfit(new int[]{1,2,3,4,5}));
        System.out.println(new Q123().maxProfit(new int[]{7,6,4,3,1,2}));
    }

    public int maxProfit(int[] prices) {
        // dp算法，带上状态，五种状态（未交易过，买过一只，卖过一只，买过两只，卖过两只）
        int s1 = Integer.MIN_VALUE,s2=Integer.MIN_VALUE,s3=Integer.MIN_VALUE,s4=Integer.MIN_VALUE;
        for (int i = 0; i < prices.length; i++) {
            s1 = Integer.max(s1, - prices[i]);
            s2 = Integer.max(s2,  s1 + prices[i]);
            s3 = Integer.max(s3, s2 - prices[i]);
            s4 = Integer.max(s4, s3 + prices[i]);
        }
        return Integer.max(s2, s4);
    }

}
